首先有一个非常 naive 的 dp。
令 表示到第 座岛的最大收益,那么有:
然后你按坐标排序,遇到纵坐标大于当前岛的直接剪掉。
这样就有 60 pts 了。
因为有坐标限制所以不好优化,考虑另一种 。
令 表示走到 的最大收益,如果没有岛为极小值。
那么转移为:
这样我们就成功把 优化转换为 了。
这是一个二维斜率优化,令 优于 ,那么有:
Chihik's Blog
首先有一个非常 naive 的 O(n2) dp。
令 dpi 表示到第 i 座岛的最大收益,那么有:
dpi=1≤j≤n,j=i,xj≤xi,yj≤yimax{dpj−(xi−xj)2−(yi−yj)2}+vi
然后你按坐标排序,遇到纵坐标大于当前岛的直接剪掉。
这样就有 60 pts 了。
因为有坐标限制所以不好优化,考虑另一种 dp。
令 dpi,j 表示走到 (i,j) 的最大收益,如果没有岛为极小值。
那么转移为:
dpi,j=1≤k≤i,1≤l≤jmax{dpk,l+(i−k)2+(j−l)2}+vi,j
dpi,j=1≤k≤i,1≤l≤jmax{dpk,l+k2−2ik+l2−2jl}+vi,j+i2+j2
这样我们就成功把 O(n2) 优化转换为 O(m4) 了。
这是一个二维斜率优化,令 (j1,j2) 优于 (k1,k2) ,那么有:
dpj1,j2+j12−2ij1+j22−2jj2<dpk1,k2+k12−2ik1+k22−2jk2
(dpj1,j2+j12+j22)−(dpk1,k2+k12+k22)<2i(j1−k1)+2j(j2−k2)
扫码打赏,你说多少就多少
打开微信扫一扫,即可进行扫码打赏哦